package com.zxlfysj.dac;

/**
 * 汉诺塔 - 分治算法
 *
 * @author yangshujing
 * @create 2020-08-25 10:51
 */
public class HanoiTower {
    public static void main(String[] args) {
        hanoiTower(3, 'A', 'B', 'C');

    }

    public static void hanoiTower(int num, char a, char b, char c) {
        if(num == 1) {
            System.out.println("第1个盘从" + a + "->" + c);
        } else {
            //把最下面一个盘看做盘2，其它盘看做盘1，
            //分解为把其他盘从a->b,移动过程使用到c，再把最下面的盘2从a->c
            //不断递归执行
            hanoiTower(num - 1, a, c, b);   //把num - 1盘即最上面的盘利用c从a移动到b
            System.out.println("第" + num + "个盘从" + a + "->" + c);   //最下面的盘从a移动到c
            hanoiTower(num - 1,b, a, c);    //把num - 1个盘利用a从b移动到c
        }

    }
}
